// 分治思想 O(nlogn) O(n) 稳定
// 递归实现
function _mergeSort(arr, start, end, temp) {
    if(start >= end) return
    let middle = Math.floor((start + end) / 2)
    _mergeSort(arr, start, middle, temp)
    _mergeSort(arr, middle + 1, end, temp)
    let start1 = start, start2 = middle + 1
    let end1 = middle, end2 = end
    let index = start
    while(start1 <= end1 && start2 <= end2) {
        // 比较大小
        if(arr[start1] < arr[start2]) {
            temp[index++] = arr[start1++]
        } else {
            temp[index++] = arr[start2++]
        }
    }
    while(start1 <= end1) {
        temp[index++] = arr[start1++]
    }
    while(start2 <= end2) {
        temp[index++] = arr[start2++]
    }
    // 完成部分归并，更新arr
    for(let i = start; i <= end; i++) {
        arr[i] = temp[i]
    }
}
let arr = [9, 4, 6, 2, 1, 1, 8]
let temp = new Array(arr.length) // 存储排序后的数组
_mergeSort(arr, 0, arr.length - 1, temp)
console.log(arr);